package com.ztom.daily.n2022.m5;

import java.util.ArrayList;
import java.util.List;

/**
 * 数组中重复的数据
 * <p>
 * https://leetcode-cn.com/problems/find-all-duplicates-in-an-array/
 *
 * @author ZhangTao
 */
public class Day08FindDuplicates {

    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        int n = nums.length;
        // 数据范围在 [1, n], 将 x = nums[i] 与 x - 1 位置相关联起来
        for (int i = 0; i < n; i++) {
            int x = Math.abs(nums[i]);
            if (nums[x - 1] > 0) {
                nums[x - 1] *= -1;
            } else {
                res.add(x);
            }
        }
        return res;
    }
}
